The present invention relates to the encoding of symbolic data, and more particularly is primarily a method of xe2x80x9cself-encodingxe2x80x9d data symbols for transmission over a spread-spectrum communication system such as code-division-multiple-access (CDMA) or frequency-division-multiple-acess (FDMA) communication systems. Said method comprises utilization of encountered data symbols in a sequence of data symbols, to develop data symbol energy spreading codes which are applied to encode subsequently encountered data symbols. Said method further includes decoding each encoded data symbol, after it is transmitted over a communications transmission system.
Both the telecommunications Industry and the military are very interested in efficient wireless electronic communication systems which maximize the number of users simultaneously served, in available bandwidth. For instance, the telecommunications industry has special interest in efficient wireless and mobile systems for application in multi-user cellular systems, and the military is particularly interested in wireless communication systems which are secure in hostile environments, have a low probability of detection, and which are not subject to being easily jammed.
Continuing, typical electronic communication systems provide a frequency bandwidth within which a multiplicity of individual communication signals are transmitted. Many well known communication systems utilize a frequency allocation approach such as frequency-division-multiplexed (FDM), wherein an available frequency bandwidth is divided into specific smaller bands, called channels, which channels are separated from one another by guard-bands. Likewise, time-division-multiplexed (TDMA) communication systems divide a period of time into a number of specific slots which sequentially carry different individual communications. In use each said channel typically carries a signal specific to a single user only. Alternative communication systems provide that a multiplicity of users simultaneously be provided access to an entire available bandwidth, and that each user""s signal be somehow encoded so that it can be later selected out from all co-present signals. Such communications systems utilize an approach which is known as xe2x80x9cSpread-Spectrumxe2x80x9d, including for instance, code-division-multiple-access (CDMA)). It is well known then that spread spectrum communication systems operate by allowing many users to share a relatively large common bandwidth in an electronic communication system in conjunction with encoding techniques such as Code Division Multiple Access (CDMA), instead of providing many separate smaller bandwidth channels, each of which carries a single user""s communication, as in (FDM).
It is noted at this point that the present invention finds primary, but not limiting, application in code-division-multiple-access (CDMA) based spread-spectrum communications systems. In that light, and as will be appreciated by those skilled in the art, it is noted that conventional wireless code-division-multiple-access (CDMA) spread spectrum electronic communication systems are designed according to the IS-95 standard for cellular telephony and personal communication services (PCS), and use Walsh Codes and m-sequences for mobile channels. Such systems presently provide that original data symbols input thereto be encoded by a method which is mediated by use of a pre-generated, determined, psuedo-random code, (rather than by a xe2x80x9cself-encodingxe2x80x9dapproach), to encode original data symbols at a transmitter, and to decode spread spectrum data symbol chips, (which were encoded utilizing said pre-generated determined psuedo-random code) at a receiver. Said psuedo-random code generation is typically achieved by expansion of a same xe2x80x9cdata keyxe2x80x9d at both transmitter and receiver locations prior to use thereof. Said psuedo-random codes generated at the transmitter and receiver are, prior to use, synchronized, and said transmitter and receiver respectively serve to direct the conversion of each of M encountered data symbols into N encoded spread spectrum data symbol chips, and re-constitution of said N encoded spread spectrum data symbol chips into the M original data symbols.
With an eye to the present invention a Search of Patents was performed which focused on use of Data to encode itself in Spread Spectrum and particularly in CDMA communication system settings, with the result of said search being that very little was found.
U.S. Pat. No. 5,343,494 to Averst et al., describes a method for receiving and processing data in a portable transceiver which involves receiving at least one information signal; decoding the at least one information signal to recover information therein; generating a plurality of pseudo-noise (PN) sequences in accordance with the information wherein each of the plurality of PN sequences is indicative of a predetermined response. The Disclosure of the 494 Patent makes it clear that xe2x80x9cgenerating a plurality of pseudo-noise (PN) sequences in accordance with the informationxe2x80x9d is to be interpreted in light of selecting one of a plurality of base station (PN) sequences so that lesser strength base station signals do not interfere. It is noted that the 494 Patent does not remotely describe reforming a transmitter spreading code with each new input symbol, to ready it for application in spreading a sequentially following data symbol, with a reverse operation applied at the receiver.
U.S. Pat. No. 5,757,853 to Tsujimoto describes using a plurality of spreading and de-spreading codes to the end that multipath fading and the like are overcome.
U.S. Pat. No. 5,467,368 to Takeuchi et al., (Col. 3, Line 67), alludes to the concept of using different spreading codes for different symbols in a sequence of symbols, however such is In the context of using a spreading code that is greater in length than the data symbols.
U.S. Patent No. 4,597,087 to Kadin describes producing first and second pseudo-noise (PN) code streams time displaced with respect to each other, and use thereof to encode data by groupings of randomly occurring frequencies and spacings therebetween. The 087 Patent also use of a frequency hopping rate equal to n times the rate of binary data being transmitted. Said 007 Patent, however, does not describe a technique of producing a (PN) code on a data symbol by symbol basis, for use in encoding subsequent data symbols.
U.S. Pat. No. 5,073,899 to Collier et al., (in Col. 3, Line 65 and thereafter), states that a pseudo-random code can be changed regularly or at irregular intervals. It describes application to pages of text. Said 899 Patent, however, provides for inclusion of a synchronization signal in a modulated signal as easily gleened from claim 1 therein.
U.S. Pat. No. 4,651,327 to Fujita describes a technique by which need for a synchronization signal can be avoided.
U.S. Pat. No. 5,495,509 to Lundquist et al., describes use of a short preamble (PN) code sequence to allow synchronization.
A lengthy Patent to Flammer, U.S. Pat. No. 5,130,987 focuses synchronization, but of information in a packet communication format on a plurality of frequencies without use of a central timing source.
U.S. Pat. No. 5,689,525 to Takeishi et al., describes generating a (PN) code based upon a delayed clock signal.
U.S. Pat. No. 5,745,522 to Heegard mentions a shift register and use of XOR to produce a pseudo-random noise sequence, operating on a byte by byte basis. Somewhat similar invention(s) is/are described in U.S. Pat. Nos. 5,410,586 and 5,260,967 to Schilling.
Additionally, a Patent to Gilhousen et al., (assigned to QUALCOMM), U.S. Pat. No. 4,901,307, was provided by the Searcher, as were Patents to Kadin, No. 4,606,041; Takeuchi et al., U.S. Pat. No. 5,467,368; U.S. Pat. No. 5,410,568 to Schilling; U.S. Pat. No. 5,260,967 to Schilling; U.S. Pat. No. 5,598,429 to Marshall; Patent U.S. Pat. No. 5,090,023 to Watanabe et al.; and U.S. Pat. No. 5,121,408 to Cai et al.
In addition, non-Patent references which are relevant and which are incorporated hereinto by reference for general background are:
xe2x80x9cA Mathematical Theory of Communicationxe2x80x9d, Bell System Technical Journal, 27, pp. 379-423 and 623-656, (1948);
xe2x80x9cSpread Spectrum Systemsxe2x80x9d, R.C. Dixon, John Wiley and Sons, (1984);
xe2x80x9cCDMA: Principals of Spread-Spectrum Communicationxe2x80x9d, A.J.
Viterbi, Addison-Wesley, (1995);
xe2x80x9cMultiple Access Communications, Foundations for Emerging Technologiesxe2x80x9d, N. Abramson, pp. 219-226, IEEE Press (1993); and
xe2x80x9cCrosscorrelation Properties of Psuedo-Random and Related Sequencesxe2x80x9d, D. V. Sarwate and M. B. Pursley, Proceedings of the IEEE, 68, pp 593-619 (May 1980).
In view of the known prior art, it is evident that the application of encountered symbolic data to continuously change a data symbol energy spreading code utilized to encode, and subsequently decode, sequentially encountered symbolic data, has not previously been reported in the context of spread-spectrum communications systems, and particularly in the context of (CDMA) communications systems and methods.
In contrast to Spread Spectrum, and in particular (CDMA) communication systems, described in known prior art, the present invention is primarily a method of practicing spread spectrum communication which comprises the transformation of a sequence of M original data symbols into a sequence of M xe2x80x9cself-encodedxe2x80x9d spread spectrum data symbols, wherein each of said self-encoded spread spectrum data symbols comprises N data symbol chips of +1, xe2x88x921, (or 0) magnitude under one typical approach, and of varying frequencies in a xe2x80x9cfrequency-hoppingxe2x80x9d approach. The present invention method further comprises transmitting the resulting sequence of said N self-encoded spread spectrum data symbol chips, and the receiving and sequential re-constitution of each of said N self-encoded spread spectrum data symbol chips, into a sequence of M original data symbols at said receiver.
The present invention method of encoding original data symbols-differs from said methods practiced by said known spread a spectrum communication systems in that a determined psuedo-random code is not necessarily, (but can be), pre-generated at either the transmitter or receiver, but a dynamic data symbol energy spreading xe2x80x9cencoding sequencexe2x80x9d is continuously generated at the transmitter side of a spread spectrum communication system based on information original data symbol content, on an original data symbol by original data symbol basis. Said generated dynamic encoding sequence also is continuously provided at the receiver side of the spread spectrum communication system as an additional operation to the re-constitution of said original data symbols from received self-encoded data symbols. As will become clear supra herein, this assumes that a first encoding sequence of N elements is provided to both the transmitter and receiver by, for instance, a synchronizing hand-shake technique so that a first symbol can be converted into N data symbol chips by use thereof at the transmitter, and re-constituted at the receiver. (Note, xe2x80x9chand-shakingxe2x80x9d is a non-limiting example of an applicable functional technique. Use of other techniques which perform a similar function to a xe2x80x9chand-shakexe2x80x9d are within the scope of the present invention).
A simple present invention method of transforming a series of two (2) original data symbols into a sequence of two (2) self-encoded spread spectrum data symbols, each of which is comprised of a sequence of N data symbol chips, comprises the providing of a sequence of two original data symbols comprising a first original data symbol followed by a sequentially second original data symbol. This is accompanied by providing a means for containing N code elements, said means for containing N code elements having an input code element containing means and an output code element containing means with (Nxe2x88x922) additional code element containing means being sequentially present there-in-between. Said means for containing N code elements is initially loaded with an initial code comprising a sequence of N code elements, one said code element being present in each of said N code element containing means. Said means for containing N code elements is capable of shifting a code element present in a code element containing means Into an adjacent code element containing means toward said output code element containing means, and ejecting a code element present in said output code element containing means. The next step requires multiplying the first of said two original data symbols by said initial N code elements present in said means for containing N code elements, to provide a sequence of N first data symbol chips. Next a code element is derived from said first of said two original data symbols and entered to said input code element containing means in said means for containing N code elements, with consequent shifting of all code elements in each of said N code element containing means in said means for containing N code elements one position toward said output code element containing means in said means for containing N code elements, accompanied by ejection of the code element present in said output code element containing means in said means for containing N code elements. The sequentially second of said two original data symbols is then multiplied by code elements present in the means for containing N code elements to provide a sequence of N data symbol chips for said sequentially next of said two original data symbols. The end result being that a sequence of two (2) self-encoded spread spectrum data symbols are developed, each being comprised of a sequence of N data symbol chips.
Another simple present invention method of transforming a series of two (2) original data symbols into a sequence of two (2) self-encoded spread spectrum data symbols, each of which is comprised of a sequence of N data symbol chips, comprises the providing a pseudo-random sequence of numbers, and providing a sequence of two (2) original data symbols comprising a first original data symbol followed by a sequentially second original data symbol. Accompanying, a means for containing N code elements, said means for containing N code elements having an input code element containing means and an output code element containing means with (Nxe2x88x922) additional code element containing means being sequentially present there-in-between is provided. Said means for containing N code elements is initially loaded with an initial code comprising a sequence of N code elements, one said code element being present in each of said N code element containing means, said means for containing N code elements being capable of shifting a code element present in a code element containing means into an adjacent code element containing means toward said output code element containing means, and ejecting a code element present in said output code element containing means. Next an optional step of applying said initial code comprising a sequence of N code elements to said pseudo-random sequence of numbers to provide a modified initial code comprising a sequence of N code elements can be performed. This is followed by multiplying the first of said two (2) original data symbols by a selection from the group consisting of: (said initial sequence of N code elements, and said modified initial code comprising a sequence of N code elements when it is available), present in said means for containing N code elements, to provide a sequence of N first data symbol chips. Next a code element is derived from said first of said two (2) original data symbols and entering it to said input code element containing means in said means for containing N code elements, with consequent shifting of all code elements in each of said N code element containing means in said means for containing N code elements one position toward said output code element containing means in said means for containing N code elements, accompanied by ejection of the code element present in said output code element containing means in said means for containing N code elements, to provide a new sequence of N code elements. Said code elements can optionally be applied to said pseudo-random sequence of numbers to provide a modified new sequence of N code elements. The sequentially second of said two (2) original data symbols is then multiplied by a selection from the group consisting of: (said new sequence of N code elements and, said modified new sequence of N code elements where it is available), present in the means for containing N code elements to provide a sequence of N data symbol chips for said sequentially next of said two (2) original data symbols. The end result being that a sequence of two (2) self-encoded spread spectrum data symbols are developed, each being comprised of a sequence of N data symbol chips.
In a general sense the present invention is a method of encoding a sequence of M original data symbols into a sequence of M self-encoded symbols. A more general present invention method comprises providing a first encoding sequence, followed by applying said first encoding sequence to the first of said sequence of M original data symbols to provide a first self-encoded symbol. This is followed by sequentially performing the following steps for each of the remaining second through (Mxe2x88x921) original data symbols:
A. deriving a new encoding sequence using a selection from the group consisting of:
1. said first encoding sequence and at least one previously determined self-encoded data symbol, and
2. at least one previously encoded original data symbol(s) as present prior to self-encoding, but which has/have already been encoded, and a selection from the group consisting of:
said first encoding sequence; and at least one previously determined self-encoded data symbol(s); and
3. said first encoding sequence and a selection from the group consisting of:
at least one previously determined self-encoded data symbol(s); and
at least one original data symbol(s) as present prior to self-encoding, but which has/have already been encoded; and
4. for the Mxe2x88x922 original data symbol and thereafter, at least two original data symbol(s) as present prior to self-encoding, but which has/have already been encoded;
B. applying said new encoding sequence to the sequentially next of said remaining (Mxe2x88x921) original data symbols to provide a sequentially next self-encoded data symbol.
The end result of practicing said method is that a sequence of M self-encoded data symbols is developed.
A modified method of encoding a sequence of M original data symbols into a sequence of M self-encoded symbols involves combining the just recited approach to self-encoding in combination with application of the results thereof to a pseudo-random sequence of numbers begins with generating a pseudo-random sequence of numbers. This is followed by providing a first encoding sequence and applying said first encoding sequence to the psuedo-random sequence of numbers to generate a the first modified encoding sequence. Then said first modified encoding sequence is applied to a first of said sequence of M original data symbols to provide a first self-encoded symbol. This is sequentially followed by performing the following steps for each of the remaining second through (Mxe2x88x921) original data symbols:
A. deriving a new modified encoding sequence by applying a new encoding sequence to said psuedo-random number sequence, said new encoding sequence being derived using a selection from the group consisting of:
1. said first encoding sequence and at least one previously determined self-encoded data symbol, and
2. at least one previously encoded original data symbol(s) as present prior to self-encoding, but which has/have already been encoded, and a selection from the group consisting of:
said first encoding sequence and at least one previously determined self-encoded data symbol(s); and
3. said first encoding sequence and a selection from the group consisting of:
at least one previously determined self-encoded data symbol(s), and at least one original data symbol(s) as present prior to self-encoding, but which has/have already been encoded; and
4. for the Mxe2x88x922 original data symbol and thereafter, at least two original data symbol(s) as present prior to self-encoding, but which has/have already been encoded;
B. applying said new modified encoding sequence to the sequentially next of said remaining (M-1) original data symbols to provide a sequentially next self-encoded symbol;
The end result is that a sequence of M self-encoded data symbols is developed.
It is specifically disclosed that in the preferred embodiment of the present invention, each sequential original data symbol sets an encoding sequence, (eg. a sequence of N code elements), which is utilized to encode and decode the next sequential original data symbol. For instance, a provided first encoding sequence is utilized to encode a first original data symbol, then the first original data symbol is utilized to reset said first provided encoding sequence, and said reset first encoding sequence is utilized to encode the second original data symbol, and so on.
To develop the dynamic encoding sequence code the present invention utilizes a code element containing means with provision for containing N code elements. Functionally this is realized preferably as a fixed length shift register having operational characteristics which provide that the entering of a code element at the input thereof, causes the shifting of a code element present in any code element containing means thereof, into an adjacent code element containing means, toward an output code element containing means. This is accompanied by the ejection of a code element present in said output code element containing means.
A preferred method of converting each of a series of M original data symbols into a string of M self-encoded spread spectrum data symbols, each thereof being comprised of a sequence of N data symbol chips, can be more specifically described as comprising the providing of a sequence of M original data symbols comprising a first data symbol followed by a sequential plurality of (Mxe2x88x921) additional original data symbols. This is accompanied with providing a means for containing N code elements. Said means for containing N code elements has an input code element containing means and an output code element containing means with (Nxe2x88x922) additional code element containing means being sequentially present there-in-between. Said means for containing N code elements is initially loaded with an initial code comprising a sequence of N code elements, one said code element being present in each of said N code element containing means. Said means for containing N code elements is capable of shifting a code element present in a code element containing means into an adjacent code element containing means toward said output code element containing means, and ejecting a code element present in said output code element containing means. Said preferred method then provides for multiplying the first of said M original data symbols by said initial N code elements present in said means for containing N code elements, to provide a sequence of N first data symbol chips. A code element is then derived from said first of said M original data symbols and entered to said input code element containing means in said means for containing N code elements, with consequent shifting of all code elements in each of said N code element containing means in said means for containing N code elements one position toward said output code element containing means in said means for containing N code elements. This is accompanied by ejection of the code element present in said output code element containing means in said means for containing N code elements. Next the following steps are performed for each of the remaining second through (Mxe2x88x921) original data symbols:
A. multiplying the sequentially next of said M original data symbols by code elements present in the means for containing N code elements to provide a sequence of N data symbol chips for said sequentially next of said M original data symbols; and
B. deriving a code element from said sequentially next of said M original data symbols and entering it to said input code element containing means of said means for containing N code elements, with consequent shifting of all code elements in each of said N code element containing means in said means for containing N code elements one position toward said output code element containing means in said means for containing N code elements, accompanied by ejection of the code element present in said output code element containing means in said means for containing N code elements.
The end result is that a sequence of M self-encoded spread spectrum data symbols is developed, each being comprised of a sequence of N data symbol chips.
The present invention then provides that the N data symbol chips for each of said M developed self-encoded spread spectrum data symbol be transmitted and received, as can be accomplished by any known communication system means with sufficient bandwidth. A received sequence of M self-encoded spread spectrum data symbols is then re-constituted into a sequence of M original data symbols.
A preferred method of re-constituting said sequence of M original data symbols from the received transmitted developed sequence of M self-encoded spread spectrum data symbols comprises providing a second means for containing N code elements, said second means for containing N code elements having an input code element containing means and an output code element containing means with (Nxe2x88x922) additional code element containing means being sequentially present there-in-between. Said second means for containing N code elements is initially loaded with said initial sequence of N code elements, one said code element being present in each of said N code element containing means. Said second means for containing N code elements is capable of shifting a code element present in a code element containing means into an adjacent code element containing means toward said output code element containing means, and ejecting a code element present in said output code element containing means. Next, the N data symbol chips of the first of said M self-encoded spread spectrum data symbols are multiplied by corresponding code elements present in said initial code present in said second means for containing N code elements, and sequentially integrating the results to provide a re-constituted first data symbol. Next, a code element is derived from said first re-constituted data symbol and entered to said input code element containing means in said second means for containing N code elements, with consequent shifting of all code elements in each of said N code element containing means in said means for containing N code elements one position toward said output code element containing means in said means for containing N code elements, accompanied by ejection of the code element present in said output code element containing means in said means for containing N code elements. This is followed by sequentially performing the following steps for each of the remaining second through (Mxe2x88x921) self-encoded spread spectrum data symbols:
A. multiplying the N data symbol chips of the sequentially next of said M self-encoded spread spectrum data symbol by corresponding code elements present in the means for containing N code elements and sequentially integrating the results to provide a next of said re-constituted M original data symbols; and
B. deriving a code element from said next of said re-constituted M original data symbols provided in step A. and entering it to said input code element containing means of said second means for containing N code elements, with consequent shifting of all code elements in each of said N code element containing means in said second means for containing N code elements one position toward said output code element containing means in said second means for containing N code elements, accompanied by ejection of the code element present in said output code element containing means in said means for containing N code elements.
The end result is that a sequence of M re-constituted original data symbols is developed.
In view of the foregoing, it can be appreciated that a complete preferred method of achieving communication utilizing the present invention then can comprise the steps of:
1. by a present invention method providing a sequence of M self-encoded spread spectrum data symbols, each being comprised of a sequence of N data symbol chips;
2. transmitting said N data symbol chips for each of said M developed self-encoded spread spectrum data symbols;
3. receiving said transmitted N data symbol chips for each of said M developed self-encoded spread spectrum data symbols;
4. re-constituting said sequence of M original data symbols from the received transmitted developed sequence of N data chips for each of the transmitted M self-encoded spread spectrum data symbols by a present invention method.
It is noted that, typically, the steps of:
2. transmitting said N data symbol chips for each developed self-encoded spread spectrum data symbols; and
3. receiving said transmitted N data symbol chips for each developed self-encoded spread spectrum data symbols;
are, for each self-encoded spread spectrum data symbol in said sequence of M self-encoded spread spectrum data symbols, performed essentially immediately after development of said N data symbol chips for an original data symbol to provide xe2x80x9creal-timexe2x80x9d operation.
It is to be understood that the term xe2x80x9cmultiplyxe2x80x9d was used in the foregoing to describe application of a N code elements to an original data symbol, or to N data symbol chips. Said terminology is typically utilized where data chips are +1, xe2x88x921 or 0. For the purposes of this Disclosure, it is to be understood that the term xe2x80x9cmultiplyxe2x80x9d is to be interpreted to also include the situation where data chips are different frequencies, (ie. in frequency-division-multiple-access (FDMA) such as frequency hopping systems).
It is, of course, to be assumed that any method of the present invention can be practiced in two-way systems as well as one-way systems as described. That is, a terminal at which is present a transmitter can also have present a receiver, and a terminal at which is present a receiver and also have present a transmitter.
It is to be understood that, as the terminology is used herein, a data symbol chip can be a +1, xe2x88x921 or 0, or can be a sequence of frequencies.
It is further noted that the degree of security of operation against unauthorized access to information communicated utilizing the present invention depends upon the degree of randomness present in a sequence of original data symbols. In this light it is disclosed that data compression techniques can serve to make a series of raw data symbols more random by removing redundant content therefrom. The present invention therefore includes in its scope the application of data compression techniques to a sequence of original raw data, to provide a sequence of M original data symbols.
It is also noted that practice of the technique known as xe2x80x9cForward Error Correction Codingxe2x80x9d in combination with the present invention method is within the scope of the present invention.
The present invention approach to self-encoding a sequence of original data symbols can also be viewed as comprising an encryption scheme.
The present invention also comprises systems which practice the described method.
The present invention will be better understood by referenced to the Detailed Description Section of this Disclosure in conjunction with the accompanying drawings.
It is a primary purpose of the present invention to teach a method for transforming a series of M original data symbols into a sequence of M xe2x80x9cself-encodedxe2x80x9d spread spectrum data symbols, each of which is comprised of a sequence of N data symbol chips.
It is another purpose of the present invention to provide that each encoded data symbol in said sequence of M xe2x80x9cself-encodedxe2x80x9d spread spectrum data symbols, be developed by application of a code, which code depends on original data symbols in a sequence of original data symbols which preceded an original data symbol being encoded.
It is yet another purpose of the present invention to provide that each encoded data symbol in said sequence of M xe2x80x9cself-encodedxe2x80x9d spread spectrum data symbols, developed by application of a code, be de-coded by a method which depends on original data symbols in a sequence of original data symbols which preceded an original data symbol being encoded.
It is another purpose yet of the present invention to provide a new method for securing wireless transmission of digital information.